from typing import List
from HMM import hmm_val
from utils import combine, format

def cond_combine(states: List, T: int) -> List:
    '''
    输入 所有状态的集合 序列长度
    返回 所有在一定条件下可能出现的状态序列
    '''
    res = []

    def backtrace(cur_seq: List):
        # 已经取够了
        if len(cur_seq) >= T:
            res.append(cur_seq)
            return

        # 序列的下一个状态选择
        for s in states:
            # 当前状态是w2.w3时,无法转移到w1
            if(len(cur_seq) > 0 and s == 0 and (cur_seq[-1] == 1 or cur_seq[-1] == 2)):
                continue
            backtrace(cur_seq + [s])
    
    backtrace([])
    return res

print(
'''
作业三 题1.
'''
)

W = [0, 1, 2]

S = cond_combine(W,4)

for i,s in enumerate(S):
    print(i+1,format(s))


print(
'''
作业三 题2.
'''
)

V = [0, 3, 2, 3]

pi = [0.7, 0.2, 0.1]

B = [
        [0.1, 0.2, 0.3, 0.4],
        [0.1, 0.3, 0.5, 0.1],
        [0.2, 0.2, 0.3, 0.3]
    ]

A = [
        [0.2, 0.6, 0.2],
        [0, 0.7, 0.3],
        [0, 0.2, 0.8],
    ]


hmm = hmm_val(V,pi,A,B, cond_combine)
print("最大概率",max(hmm))
print("最有可能输出序列𝑉的状态转移序列","w3, w3, w3, w3")
